package normalArray;

import javax.xml.ws.soap.MTOM;

public class maxSubArray {
    // 法一：前缀和+暴力双重for
    // 超时
    public static int maxSubArray1(int[] nums) {
        if (nums.length==1) {
            return nums[0];
        }
        //maxNum初始化应该取下限
        int max = 0,maxNum=-10000;
        int[] prefixSum = new int[nums.length+1];
        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i]=prefixSum[i-1]+nums[i-1];
            maxNum=Math.max(maxNum, nums[i-1]);
        }
        // 先判断是否全为非整数
        if (maxNum<=0) {
            return maxNum;
        }
        for (int i = nums.length; i >0; i--) {
            for (int j = 0; j < i; j++) {
                if (prefixSum[i]-prefixSum[j]>max) {
                    max=prefixSum[i]-prefixSum[j];
                }
            }
        }
        // 1 2 3 -1 6
        return max;
    }
    // 变大小滑动窗口
    // 还是超时，最后还是变成双重for循环了几乎
    public static int maxSubArray2(int[] nums) {
        // 一直右移，直到小于0，left++
        if (nums.length==1) {
            return nums[0];
        }
        int left=0,right=-1,sum=0,max=-10000,maxNum=-10000;
        while (left<nums.length) {
            maxNum = Math.max(nums[left], maxNum);
            if (right==-1) {
                right++;
                sum+=nums[right];
                 max=Math.max(max, sum);
                continue;
            }
            //只要累加和>0，后面就还有机会，否则left++
            // -1,3,1-1
            while (right+1<nums.length&&sum+nums[right+1]>0) {
                right++;
                // 是否丢掉累赘
                if (sum+nums[right]<nums[right]) {
                    left=right;
                    sum=0;
                     maxNum = Math.max(nums[left], maxNum);
                }
                sum+=nums[right];
                max=Math.max(max, sum);
            }
            //left右移
            sum-=nums[left];
            max=Math.max(max, sum);
            left++;
            if (left>right&&left<nums.length) {
                right=left;
                sum=nums[right];
                max=Math.max(max, sum);
            }
            // 不能是简单的left++
            // -1,3,1,-1
            
            

        }
        // 全是负数，返回最大的那个
        if (maxNum<=0) {
            return maxNum;
        }
        return max;
    }
    // 之前想着，只要前缀和+当前元素是大于0.后面就有机会扳本。也就是是我下一个让sum变小了也没关系。
    // 但核心问题在于，移动的过程中，不会把之前的累赘丢了。比如-1,3,1,-1，right到了最后一位，即使left再移动，-1也被统计进去了
    // 所以一开始就要把累赘丢了
    public static int maxSubArray3(int[] nums){
        int pre=0,ans=nums[0];
        for(int num : nums){
            pre=Math.max(pre+num,num);
            ans=Math.max(pre, ans);
        }
        return ans;
    }
    public static void main(String[] args) {
        // int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        // int[] nums = new int[]{5,4,-1,7,8};
        // int[] nums = new int[]{-2,1};
        // int[] nums = new int[]{1,-1,-2};
        // int[] nums = new int[]{-1,3,1,-1};
        int[] nums = new int[]{0,-1,2};
        int maxSubArray = maxSubArray2(nums);
        System.out.println("rs="+maxSubArray);
    }
}
